package com.sxu.greedy.day5;

/**
 * 397 整数替换
 *  递归实现
 */
public class Test24_1 {
    public int integerReplacement(int n) {
        return dfs(n * 1L);
    }

    public int dfs(long n) {
        if(n == 1){
            return 0;
        }
        if(n%2 == 0){
            return 1 + dfs(n/2);
        } else {
            return 1 + Math.min(dfs(n-1),dfs(n+1));
        }
    }
}
